package ch4.part5;

import java.util.Arrays;

/**
 * 计数排序：适用场景需满足以下2点要求
 * 1. 数列的最大值和最小值相差较小
 * 2. 数列元素都是整数
 * <p>
 * 平均时间复杂度：O(n) = n + m
 * 最坏时间复杂度：O(n) = n + m
 * 空间复杂度：O(n) = m
 *
 * @author liuwanxiang
 * @version 2019/06/15
 */
public class CountSort {

    private static int[] sort(int[] array) {

        // 确定数组的最大值和最小值，确定计数器数组的长度和偏移量
        int min = 0, max = 0;
        for (int value : array) {
            if (min > value) {
                min = value;
            }
            if (max < value) {
                max = value;
            }
        }
        int len = max - min;

        // 构建计数器数组，元素每出现一次，该位置计数器++
        int[] localArray = new int[len + 1];
        for (int value : array) {
            localArray[value - min]++;
        }

        // 构建排序好的队列，并做返回
        int[] sortedArray = new int[array.length];
        int index = 0;
        for (int i = 0; i <= len; i++) {
            for (int j = 0; j < localArray[i]; j++) {
                sortedArray[index++] = i + min;
            }
        }
        return sortedArray;
    }

    public static void main(String[] args) {
        int[] array = {11, 10, 12, 19, 13, 16, 19, 14, 18, 17, 16, 15};
        int[] sortedArray = sort(array);
        System.out.println(Arrays.toString(sortedArray));
    }

}
